package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

/**
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 * @author lchenglong
 * @date 2022/6/16
 */
public class 环形链表II {
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode fast = head,slow = head;
            while (fast!=null && fast.next != null){
                // 快指针走两步
                fast = fast.next.next;
                // 慢指针走一步
                slow = slow.next;
                if (fast == slow)break;
            }
            // 说明无环
            if (fast == null||fast.next == null){
                return null;
            }
            // 令slow从头结点开始
            slow = head;
            // 快慢指针同步前进，相交点就是环起点
            while (slow!=fast){
                slow = slow.next;
                fast= fast.next;
            }
            return slow;
        }
    }
}
